{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Common Subpath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #suffix-array #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #后缀数组 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestCommonSubpath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最长公共子路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个国家由 <code>n</code> 个编号为 <code>0</code> 到 <code>n - 1</code> 的城市组成。在这个国家里，<strong>每两个</strong> 城市之间都有一条道路连接。</p>\n",
    "\n",
    "<p>总共有 <code>m</code> 个编号为 <code>0</code> 到 <code>m - 1</code> 的朋友想在这个国家旅游。他们每一个人的路径都会包含一些城市。每条路径都由一个整数数组表示，每个整数数组表示一个朋友按顺序访问过的城市序列。同一个城市在一条路径中可能 <strong>重复</strong> 出现，但同一个城市在一条路径中不会连续出现。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> 和二维数组 <code>paths</code> ，其中 <code>paths[i]</code> 是一个整数数组，表示第 <code>i</code> 个朋友走过的路径，请你返回 <strong>每一个</strong> 朋友都走过的 <strong>最长公共子路径</strong> 的长度，如果不存在公共子路径，请你返回 <code>0</code> 。</p>\n",
    "\n",
    "<p>一个 <strong>子路径</strong> 指的是一条路径中连续的城市序列。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, paths = [[0,1,<strong>2,3</strong>,4],\n",
    "                     [<strong>2,3</strong>,4],\n",
    "                     [4,0,1,<strong>2,3</strong>]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>最长公共子路径为 [2,3] 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 3, paths = [[0],[1],[2]]\n",
    "<b>输出：</b>0\n",
    "<b>解释：</b>三条路径没有公共子路径。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>n = 5, paths = [[<strong>0</strong>,1,2,3,4],\n",
    "                     [4,3,2,1,<strong>0</strong>]]\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>最长公共子路径为 [0]，[1]，[2]，[3] 和 [4] 。它们长度都为 1 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>m == paths.length</code></li>\n",
    "\t<li><code>2 <= m <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>sum(paths[i].length) <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 <= paths[i][j] < n</code></li>\n",
    "\t<li><code>paths[i]</code> 中同一个城市不会连续重复出现。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-common-subpath](https://leetcode.cn/problems/longest-common-subpath/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-common-subpath](https://leetcode.cn/problems/longest-common-subpath/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[0,1,2,3,4],[2,3,4],[4,0,1,2,3]]', '3\\n[[0],[1],[2]]', '5\\n[[0,1,2,3,4],[4,3,2,1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        m = len(paths)\n",
    "        base = int(1e7) + 2334\n",
    "        MOD = int(1e15) + 1\n",
    "\n",
    "        def search(k):\n",
    "            ps = set()\n",
    "            basek = pow(base, k, MOD)\n",
    "            for i in range(m):\n",
    "                p = paths[i]\n",
    "                s = set()\n",
    "                h = 0\n",
    "\n",
    "                for j in range(k):\n",
    "                    h = (h * base + p[j]) % MOD\n",
    "\n",
    "                if not ps or h in ps:\n",
    "                    s.add(h)\n",
    "                \n",
    "                for j in range(k, len(p)):\n",
    "                    h = (h * base - p[j - k] * basek + p[j]) % MOD\n",
    "\n",
    "                    if not ps or h in ps:\n",
    "                        s.add(h)\n",
    "\n",
    "                if not s:\n",
    "                    return 1\n",
    "\n",
    "                ps = s\n",
    "\n",
    "            return 0\n",
    "\n",
    "        k = bisect_right(range(1, min(len(x) for x in paths) + 1), 0, key=lambda x: search(x))\n",
    "\n",
    "        return k\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        def get_set(n, path, p, k):\n",
    "                s = set()\n",
    "                cur = 0\n",
    "                for i in range(k):\n",
    "                    cur *= n\n",
    "                    cur += path[i]\n",
    "                    cur %= p\n",
    "                s.add(cur)\n",
    "                for i in range(k, len(path)):\n",
    "                    cur *= n\n",
    "                    cur += path[i]\n",
    "                    cur -= pow(n, k, p) * path[i - k]\n",
    "                    cur %= p\n",
    "                    s.add(cur)\n",
    "                return s\n",
    "        \n",
    "        def check(n, paths, p, k):\n",
    "                s = get_set(n, paths[0], p, k)\n",
    "                for i in range(1, len(paths)):\n",
    "                    t = get_set(n, paths[i], p, k)\n",
    "                    s &= t\n",
    "                    if len(s) == 0:\n",
    "                        return False\n",
    "                return True\n",
    "\n",
    "        p = 10 ** 12 + 73\n",
    "\n",
    "        left = 0\n",
    "        right = min([len(path) for path in paths]) + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(n, paths, p, mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def get_hash_ck(self, path, ck):\n",
    "        MOD = (10**9 + 7) * (10**9 + 9)\n",
    "        P = 1333331\n",
    "        ln = len(path)\n",
    "        path = [0] + path\n",
    "        p = [1] * (ln + 1)\n",
    "        h = [0] * (ln + 1)\n",
    "        for i in range(1, ln + 1):\n",
    "            p[i] = p[i - 1] * P % MOD\n",
    "            h[i] = (h[i - 1] * P + path[i] + 1) % MOD\n",
    "        st = set()\n",
    "        for i in range(1, ln + 2 - ck):\n",
    "            x = h[i + ck - 1] - h[i - 1] * p[ck]\n",
    "            x = (x % MOD + MOD) % MOD\n",
    "            st.add(x)\n",
    "        return st\n",
    "    \n",
    "    def check(self, n, paths, ck):\n",
    "        st = self.get_hash_ck(paths[0], ck)\n",
    "        for i in range(1, len(paths)):\n",
    "            st.intersection_update(self.get_hash_ck(paths[i], ck))\n",
    "            if len(st) == 0:\n",
    "                break\n",
    "        return len(st) > 0        \n",
    "\n",
    "    \n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        l = 0\n",
    "        r = min(map(len, paths))\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) >> 1\n",
    "            if self.check(n, paths, mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        base = 100003\n",
    "        MOD = (10**9+7) * (10**9+9)\n",
    "        n = len(paths)\n",
    "\n",
    "        def check(k):\n",
    "            cnt = defaultdict(int)\n",
    "            for path in paths:\n",
    "                vis = set()\n",
    "                val = 0\n",
    "                for i in range(k):\n",
    "                    val = (val * base + path[i]) % MOD\n",
    "                p = pow(base, k, MOD)\n",
    "                vis.add(val)\n",
    "                for i in range(k, len(path)):\n",
    "                    val = (val * base + path[i] - p * path[i-k]) % MOD\n",
    "                    vis.add(val)\n",
    "                for val in vis:\n",
    "                    cnt[val] += 1\n",
    "            return max(cnt.values()) == n\n",
    "\n",
    "        l, r = 0, min(len(path) for path in paths)\n",
    "        while l < r:\n",
    "            mid = (l + r + 1) // 2\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        mo = (10 ** 9 + 7) * (10 ** 9 + 5)\n",
    "        base = random.randint(10**6, 10**7)\n",
    "        m = len(paths)\n",
    "        left, right, ans = 1, len(min(paths, key = lambda p: len(p))), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            mult = pow(base, mid, mo)\n",
    "            s = set()\n",
    "            check = True\n",
    "\n",
    "            for i in range(m):\n",
    "                hashvalue = 0\n",
    "                for j in range(mid):\n",
    "                    hashvalue = (hashvalue * base + paths[i][j]) % mo\n",
    "                t = set()\n",
    "                if i == 0 or hashvalue in s:\n",
    "                    t.add(hashvalue)\n",
    "                for j in range(mid, len(paths[i])):\n",
    "                    hashvalue = (hashvalue * base - paths[i][j - mid] * mult + paths[i][j] + mo) % mo\n",
    "                    if i == 0 or hashvalue in s:\n",
    "                        t.add(hashvalue)\n",
    "                if not t:\n",
    "                    check = False\n",
    "                    break\n",
    "                s = t\n",
    "\n",
    "            if (check):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        p, q = 133331, (1<<64) + 1\n",
    "        def check(m):\n",
    "            multi = pow(p, m, q)\n",
    "            pre = set()\n",
    "            for j, path in enumerate(paths):\n",
    "                cur = set()\n",
    "                #[3,5,6] = 356\n",
    "                h = 0\n",
    "                for i in range(m):\n",
    "                    h = (h * p + path[i]) % q\n",
    "                if j == 0 or h in pre:\n",
    "                    cur.add(h)  \n",
    "                for i in range(1, len(path) - m + 1):\n",
    "                    h = (h * p - path[i - 1] * multi + path[m - 1 + i]) % q\n",
    "                    if j == 0 or h in pre:\n",
    "                        cur.add(h)\n",
    "                # print(f'{m,pre,cur,path,h}')\n",
    "                if not cur:\n",
    "                    return False\n",
    "                pre = cur\n",
    "            return True\n",
    "        l, r = 0, len(min(paths, key=lambda x:len(x)))\n",
    "        # print(f'{l},{r}')\n",
    "        while l < r:\n",
    "            m = l + r + 1 >> 1\n",
    "            if check(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        # 根据正文部分的分析，我们选择的 mod 需要远大于 10^10\n",
    "        # Python 直接选择 10^9+7 * 10^9+9 作为模数即可\n",
    "        # 乘积约为 10^18，远大于 10^10\n",
    "        mod = (10**9 + 7) * (10**9 + 9)\n",
    "\n",
    "        # 本题中数组元素的范围为 [0, 10^5]\n",
    "        # 因此我们在 [10^6, 10^7] 的范围内随机选取进制 base\n",
    "        base = random.randint(10**6, 10**7)\n",
    "        \n",
    "        m = len(paths)\n",
    "        # 确定二分查找的上下界\n",
    "        left, right, ans = 1, len(min(paths, key=lambda p: len(p))), 0\n",
    "        while left <= right:\n",
    "            length = (left + right) // 2\n",
    "            mult = pow(base, length, mod)\n",
    "            s = set()\n",
    "            check = True\n",
    "\n",
    "            for i in range(m):\n",
    "                hashvalue = 0\n",
    "                # 计算首个长度为 len 的子数组的哈希值\n",
    "                for j in range(length):\n",
    "                    hashvalue = (hashvalue * base + paths[i][j]) % mod\n",
    "\n",
    "                t = set()\n",
    "                # 如果我们遍历的是第 0 个数组，或者上一个数组的哈希表中包含该哈希值\n",
    "                # 我们才会将哈希值加入当前数组的哈希表中\n",
    "                if i == 0 or hashvalue in s:\n",
    "                    t.add(hashvalue)\n",
    "                # 递推计算后续子数组的哈希值\n",
    "                for j in range(length, len(paths[i])):\n",
    "                    hashvalue = (hashvalue * base - paths[i][j - length] * mult + paths[i][j]) % mod\n",
    "                    if i == 0 or hashvalue in s:\n",
    "                        t.add(hashvalue)\n",
    "                if not t:\n",
    "                    check = False\n",
    "                    break\n",
    "                s = t\n",
    "            \n",
    "            if check:\n",
    "                ans = length\n",
    "                left = length + 1\n",
    "            else:\n",
    "                right = length - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = (10**9 + 7) * (10**9 + 9)\n",
    "base = random.randint(10**6, 10**7)\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        m = len(paths)\n",
    "\n",
    "        def check(mid):\n",
    "            mult = pow(base, mid, kmod)\n",
    "            s = set()\n",
    "            for i in range(m):\n",
    "                hv = 0\n",
    "                for j in range(mid):\n",
    "                    hv = (hv * base + paths[i][j]) % kmod\n",
    "                \n",
    "                t = set()\n",
    "                if i == 0 or hv in s:\n",
    "                    t.add(hv)\n",
    "                for j in range(mid, len(paths[i])):\n",
    "                    hv = (hv * base - paths[i][j - mid] * mult + paths[i][j]) % kmod\n",
    "                    if i == 0 or hv in s:\n",
    "                        t.add(hv)\n",
    "                if not t:\n",
    "                    return False\n",
    "                s = t\n",
    "\n",
    "            return True\n",
    "\n",
    "        l, r = 1, min(len(paths[i]) for i in range(m))\n",
    "        return bisect_left(range(r + 1), 1, l, key=lambda t:not check(t)) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        mod = (10**9 + 7) * (10**9 + 9)\n",
    "        base = random.randint(10**6, 10**7)\n",
    "        m = len(paths)\n",
    "        left, right, ans = 1, len(min(paths, key=lambda p: len(p))), 0\n",
    "        while left <= right:\n",
    "            length = (left + right) // 2\n",
    "            mult = pow(base, length, mod)\n",
    "            s = set()\n",
    "            check = True\n",
    "\n",
    "            for i in range(m):\n",
    "                hashvalue = 0\n",
    "                for j in range(length):\n",
    "                    hashvalue = (hashvalue * base + paths[i][j]) % mod\n",
    "                t = set()\n",
    "                if i == 0 or hashvalue in s:\n",
    "                    t.add(hashvalue)\n",
    "                for j in range(length, len(paths[i])):\n",
    "                    hashvalue = (hashvalue * base - paths[i][j - length] * mult + paths[i][j]) % mod\n",
    "                    if i == 0 or hashvalue in s:\n",
    "                        t.add(hashvalue)\n",
    "                if not t:\n",
    "                    check = False\n",
    "                    break\n",
    "                s = t\n",
    "            if check:\n",
    "                ans = length\n",
    "                left = length + 1\n",
    "            else:\n",
    "                right = length - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, ps: List[List[int]]) -> int:\n",
    "        '''双hash'''\n",
    "        def dhash(m, p, s):\n",
    "            p1, p2, b1, b2 = 10 ** 9 + 7, 10 ** 9 + 9, 131, 13331  # 双哈希：两套进制\n",
    "            n, h1, h2, hs = len(p), 0, 0, set()\n",
    "            b=len(s)==0\n",
    "            qp1, qp2 = pow(b1, m, p1), pow(b2, m, p2)\n",
    "            for i in range(m):\n",
    "                h1 = (h1 * b1 + p[i]) % p1\n",
    "                h2 = (h2 * b2 + p[i]) % p2\n",
    "            if b or (h1,h2) in s:hs.add((h1,h2))\n",
    "            for i in range(m, n):\n",
    "                c1, c2 = i - m, i\n",
    "                h1 = (h1 * b1 % p1 - p[c1] * qp1 % p1 + p[c2]) % p1\n",
    "                h2 = (h2 * b2 % p2 - p[c1] * qp2 % p2 + p[c2]) % p2\n",
    "                if h1 < 0: h1 += p1\n",
    "                if h2 < 0: h2 += p2\n",
    "                if b or (h1, h2) in s: hs.add((h1,h2))\n",
    "            return hs\n",
    "        l,r=0,10**6\n",
    "        for p in ps:r=min(len(p),r)\n",
    "        r+=1\n",
    "        m=len(ps)\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            ok=True\n",
    "            s=dhash(mid,ps[0],set())\n",
    "            for i in range(1,m):\n",
    "                if len(ps[i])<mid:\n",
    "                    ok=False\n",
    "                    break\n",
    "                s=dhash(mid, ps[i],s)\n",
    "                if len(s)==0:\n",
    "                    ok=False\n",
    "                    break\n",
    "            if ok:\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        # 根据正文部分的分析，我们选择的 mod 需要远大于 10^10\n",
    "        # Python 直接选择 10^9+7 * 10^9+9 作为模数即可\n",
    "        # 乘积约为 10^18，远大于 10^10\n",
    "        mod = (10**9 + 7) * (10**9 + 9)\n",
    "\n",
    "        # 本题中数组元素的范围为 [0, 10^5]\n",
    "        # 因此我们在 [10^6, 10^7] 的范围内随机选取进制 base\n",
    "        base = random.randint(10**6, 10**7)\n",
    "        \n",
    "        m = len(paths)\n",
    "        # 确定二分查找的上下界\n",
    "        left, right, ans = 1, len(min(paths, key=lambda p: len(p))), 0\n",
    "        while left <= right:\n",
    "            length = (left + right) // 2\n",
    "            mult = pow(base, length, mod)\n",
    "            s = set()\n",
    "            check = True\n",
    "\n",
    "            for i in range(m):\n",
    "                hashvalue = 0\n",
    "                # 计算首个长度为 len 的子数组的哈希值\n",
    "                for j in range(length):\n",
    "                    hashvalue = (hashvalue * base + paths[i][j]) % mod\n",
    "\n",
    "                t = set()\n",
    "                # 如果我们遍历的是第 0 个数组，或者上一个数组的哈希表中包含该哈希值\n",
    "                # 我们才会将哈希值加入当前数组的哈希表中\n",
    "                if i == 0 or hashvalue in s:\n",
    "                    t.add(hashvalue)\n",
    "                # 递推计算后续子数组的哈希值\n",
    "                for j in range(length, len(paths[i])):\n",
    "                    hashvalue = (hashvalue * base - paths[i][j - length] * mult + paths[i][j]) % mod\n",
    "                    if i == 0 or hashvalue in s:\n",
    "                        t.add(hashvalue)\n",
    "                if not t:\n",
    "                    check = False\n",
    "                    break\n",
    "                s = t\n",
    "            \n",
    "            if check:\n",
    "                ans = length\n",
    "                left = length + 1\n",
    "            else:\n",
    "                right = length - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        P, Q = 133331, (1 << 64) + 1\n",
    "        \n",
    "        def check(mid):\n",
    "            multi = pow(P, mid, Q)\n",
    "            pre = set()\n",
    "            for i, path in enumerate(paths):\n",
    "                cur = set()\n",
    "                hv = 0\n",
    "                for j in range(mid):\n",
    "                    hv = (hv * P + path[j]) % Q\n",
    "                if i == 0 or hv in pre:\n",
    "                    cur.add(hv)\n",
    "                \n",
    "                for j in range(mid, len(path)):\n",
    "                    hv = (hv * P - path[j - mid] * multi + path[j]) % Q\n",
    "                    if i == 0 or hv in pre:\n",
    "                        cur.add(hv)\n",
    "                if not cur:\n",
    "                    return False\n",
    "                pre = cur\n",
    "            return True\n",
    "        \n",
    "        l, r = 0, len(min(paths, key=lambda x: len(x)))\n",
    "        while l < r:\n",
    "            mid = l + r + 1 >> 1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, ps: List[List[int]]) -> int:\n",
    "        '''双hash'''\n",
    "        def dhash(m, p, s):\n",
    "            p1, p2, b1, b2 = 10 ** 9 + 7, 10 ** 9 + 9, 131, 13331  # 双哈希：两套进制\n",
    "            n, h1, h2, hs = len(p), 0, 0, set()\n",
    "            b=len(s)==0\n",
    "            qp1, qp2 = pow(b1, m, p1), pow(b2, m, p2)\n",
    "            for i in range(m):\n",
    "                h1 = (h1 * b1 + p[i]) % p1\n",
    "                h2 = (h2 * b2 + p[i]) % p2\n",
    "            if b or (h1,h2) in s:\n",
    "                hs.add((h1,h2))\n",
    "            for i in range(m, n):\n",
    "                c1, c2 = i - m, i\n",
    "                h1 = (h1 * b1 % p1 - p[c1] * qp1 % p1 + p[c2]) % p1\n",
    "                if h1 < 0: h1 += p1\n",
    "                h2 = (h2 * b2 % p2 - p[c1] * qp2 % p2 + p[c2]) % p2\n",
    "                if h2 < 0: h2 += p2\n",
    "                if b or (h1, h2) in s: hs.add((h1,h2))\n",
    "            return hs\n",
    "        l,r=0,10**6\n",
    "        for p in ps:\n",
    "            r=min(len(p),r)\n",
    "        r+=1\n",
    "        m=len(ps)\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            ok=True\n",
    "            s=dhash(mid,ps[0],set())\n",
    "            for i in range(1,m):\n",
    "                if len(ps[i])<mid:\n",
    "                    ok=False\n",
    "                    break\n",
    "                s=dhash(mid, ps[i],s)\n",
    "                if len(s)==0:\n",
    "                    ok=False\n",
    "                    break\n",
    "            if ok:\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "      # P和Q为字符串哈希的关键词\n",
    "      P,Q=133331,(1<<64)+1\n",
    "      m=len(paths)\n",
    "      N=100010\n",
    "      p=[1]*N\n",
    "      h=[0]*N\n",
    "      # 获取区间字符串对应的哈希值\n",
    "      def get(l,r):\n",
    "          return (h[r]-h[l-1]*p[r-l+1])%Q\n",
    "\n",
    "      # 判断是否存在长度为mid的公共子串\n",
    "      def check(mid):\n",
    "        cnt=Counter()      \n",
    "        \n",
    "        for v in paths:\n",
    "            visited=set()\n",
    "            size=len(v)\n",
    "            for i in range(size):\n",
    "                p[i+1]=p[i]*P%Q\n",
    "                h[i+1]=(h[i]*P+v[i])%Q\n",
    "            for i in range(mid,size+1):\n",
    "                t=get(i-mid+1,i)\n",
    "                if t not in visited:\n",
    "                    visited.add(t)\n",
    "                    cnt[t]+=1\n",
    "        return max(cnt.values())==m\n",
    "            \n",
    "      # 二分满足条件的公共子串长度\n",
    "      l,r=0,len(min(paths,key=lambda x:len(x)))\n",
    "      while l<r:\n",
    "        mid=l+(r-l+1)//2\n",
    "        if check(mid):\n",
    "          l=mid\n",
    "        else:\n",
    "          r=mid-1\n",
    "      return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "      # P和Q为字符串哈希的关键词\n",
    "      P=133331\n",
    "      Q=(1<<64)+1\n",
    "      m=len(paths)\n",
    "      N=100010\n",
    "      p=[1]*N\n",
    "      h=[0]*N\n",
    "      # 获取区间字符串对应的哈希值\n",
    "      def get(l,r):\n",
    "          return (h[r]-h[l-1]*p[r-l+1])%Q\n",
    "\n",
    "      # 判断是否存在长度为mid的公共子串\n",
    "      def check(mid):\n",
    "        cnt=Counter()      \n",
    "        \n",
    "        for v in paths:\n",
    "            visited=set()\n",
    "            size=len(v)\n",
    "            for i in range(size):\n",
    "                p[i+1]=p[i]*P%Q\n",
    "                h[i+1]=(h[i]*P+v[i])%Q\n",
    "            for i in range(mid,size+1):\n",
    "                t=get(i-mid+1,i)\n",
    "                if t not in visited:\n",
    "                    visited.add(t)\n",
    "                    cnt[t]+=1\n",
    "        return max(cnt.values())==m\n",
    "            \n",
    "      # 二分满足条件的公共子串长度\n",
    "      l=0\n",
    "      r=len(min(paths,key=lambda x:len(x)))\n",
    "      while l<r:\n",
    "        mid=l+(r-l+1)//2\n",
    "        if check(mid):\n",
    "          l=mid\n",
    "        else:\n",
    "          r=mid-1\n",
    "      return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "P = 102983\n",
    "MOD = 6177324851776706557\n",
    "\n",
    "PX = [1]\n",
    "t = 1\n",
    "for i in range(10 ** 5):\n",
    "    t *= P\n",
    "    t %= MOD\n",
    "    PX.append(t)\n",
    "\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        m = len(paths)\n",
    "        phash = [[0] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            h = 0\n",
    "            for x in paths[i]:\n",
    "                h *= P\n",
    "                h += x\n",
    "                h %= MOD\n",
    "                phash[i].append(h)\n",
    "        \n",
    "        def f(l: int) -> bool:\n",
    "            t = None\n",
    "            for i in range(m):\n",
    "                s = set()\n",
    "                for j in range(l, len(paths[i]) + 1):\n",
    "                    h = (phash[i][j] - phash[i][j - l] * PX[l]) % MOD\n",
    "                    s.add(h)\n",
    "                if t == None:\n",
    "                    t = s\n",
    "                else:\n",
    "                    t &= s\n",
    "                if len(t) == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        \n",
    "        l = 0\n",
    "        r = min(len(paths[i]) for i in range(m))\n",
    "        #for i in range(l, r + 1):\n",
    "        #    print(i, f(i))\n",
    "\n",
    "        while l < r - 1:\n",
    "            mid = (l + r) // 2\n",
    "            if f(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        \n",
    "        if f(r):\n",
    "            return r\n",
    "        else:\n",
    "            return l\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class SuffixArray:\n",
    "    def sa_naive(self, s):       #实现了最朴素的后缀数组构建算法，其时间复杂度为 O(n^2 log n)，适用于小规模字符串。\n",
    "        n = len(s)\n",
    "        sa = list(range(n))\n",
    "        sa.sort(key=lambda x: s[x:])\n",
    "        return sa\n",
    "\n",
    "    def sa_doubling(self, s):    #实现了倍增算法，其时间复杂度为 O(n log n)，适用于中等规模字符串。\n",
    "        n = len(s)\n",
    "        sa = list(range(n))\n",
    "        rnk = s\n",
    "        t = [0] * n\n",
    "        k = 1\n",
    "        while k < n:\n",
    "            sa.sort(key=lambda x: (rnk[x], rnk[x + k])\n",
    "            if x + k < n else (rnk[x], -1))\n",
    "            t[sa[0]] = 0\n",
    "            for i in range(1, n):\n",
    "                t[sa[i]] = t[sa[i - 1]]\n",
    "                if sa[i - 1] + k < n:\n",
    "                    x = (rnk[sa[i - 1]], rnk[sa[i - 1] + k])\n",
    "                else:\n",
    "                    x = (rnk[sa[i - 1]], -1)\n",
    "                if sa[i] + k < n:\n",
    "                    y = (rnk[sa[i]], rnk[sa[i] + k])\n",
    "                else:\n",
    "                    y = (rnk[sa[i]], -1)\n",
    "                if x < y:\n",
    "                    t[sa[i]] += 1\n",
    "            k *= 2\n",
    "            t, rnk = rnk, t\n",
    "        return sa\n",
    "\n",
    "    def sa_is(self, s, upper):\n",
    "        #实现了 SA-IS 算法，其时间复杂度为 O(n)，适用于大规模字符串。\n",
    "        #SA-IS 算法基于桶排思想，通过对字符串进行分类和排序，最终得到后缀数组。\n",
    "        #代码中使用了类似于桶排的技巧，通过计算各种类型的后缀数量和前缀相同的子串，将问题转化为子问题，然后递归求解。\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return []\n",
    "        if n == 1:\n",
    "            return [0]\n",
    "        if n == 2:\n",
    "            if s[0] < s[1]:\n",
    "                return [0, 1]\n",
    "            else:\n",
    "                return [1, 0]\n",
    "        if n < 10:\n",
    "            return self.sa_naive(s)\n",
    "        if n < 50:\n",
    "            return self.sa_doubling(s)\n",
    "        ls = [0] * n\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ls[i] = ls[i + 1] if s[i] == s[i + 1] else s[i] < s[i + 1]\n",
    "        sum_l = [0] * (upper + 1)\n",
    "        sum_s = [0] * (upper + 1)\n",
    "        for i in range(n):\n",
    "            if ls[i]:\n",
    "                sum_l[s[i] + 1] += 1\n",
    "            else:\n",
    "                sum_s[s[i]] += 1\n",
    "        for i in range(upper):\n",
    "            sum_s[i] += sum_l[i]\n",
    "            if i < upper:\n",
    "                sum_l[i + 1] += sum_s[i]\n",
    "        lms_map = [-1] * (n + 1)\n",
    "        m = 0\n",
    "        for i in range(1, n):\n",
    "            if not ls[i - 1] and ls[i]:\n",
    "                lms_map[i] = m\n",
    "                m += 1\n",
    "        lms = []\n",
    "        for i in range(1, n):\n",
    "            if not ls[i - 1] and ls[i]:\n",
    "                lms.append(i)\n",
    "        sa = [-1] * n\n",
    "        buf = sum_s.copy()\n",
    "        for d in lms:\n",
    "            if d == n:\n",
    "                continue\n",
    "            sa[buf[s[d]]] = d\n",
    "            buf[s[d]] += 1\n",
    "        buf = sum_l.copy()\n",
    "        sa[buf[s[n - 1]]] = n - 1\n",
    "        buf[s[n - 1]] += 1\n",
    "        for i in range(n):\n",
    "            v = sa[i]\n",
    "            if v >= 1 and not ls[v - 1]:\n",
    "                sa[buf[s[v - 1]]] = v - 1\n",
    "                buf[s[v - 1]] += 1\n",
    "        buf = sum_l.copy()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            v = sa[i]\n",
    "            if v >= 1 and ls[v - 1]:\n",
    "                buf[s[v - 1] + 1] -= 1\n",
    "                sa[buf[s[v - 1] + 1]] = v - 1\n",
    "        if m:\n",
    "            sorted_lms = []\n",
    "            for v in sa:\n",
    "                if lms_map[v] != -1:\n",
    "                    sorted_lms.append(v)\n",
    "            rec_s = [0] * m\n",
    "            rec_upper = 0\n",
    "            rec_s[lms_map[sorted_lms[0]]] = 0\n",
    "            for i in range(1, m):\n",
    "                l = sorted_lms[i - 1]\n",
    "                r = sorted_lms[i]\n",
    "                end_l = lms[lms_map[l] + 1] if lms_map[l] + 1 < m else n\n",
    "                end_r = lms[lms_map[r] + 1] if lms_map[r] + 1 < m else n\n",
    "                same = True\n",
    "                if end_l - l != end_r - r:\n",
    "                    same = False\n",
    "                else:\n",
    "                    while l < end_l:\n",
    "                        if s[l] != s[r]:\n",
    "                            break\n",
    "                        l += 1\n",
    "                        r += 1\n",
    "                    if l == n or s[l] != s[r]:\n",
    "                        same = False\n",
    "                if not same:\n",
    "                    rec_upper += 1\n",
    "                rec_s[lms_map[sorted_lms[i]]] = rec_upper\n",
    "            rec_sa = self.sa_is(rec_s, rec_upper)\n",
    "            for i in range(m):\n",
    "                sorted_lms[i] = lms[rec_sa[i]]\n",
    "            sa = [-1] * n\n",
    "            buf = sum_s.copy()\n",
    "            for d in sorted_lms:\n",
    "                if d == n:\n",
    "                    continue\n",
    "                sa[buf[s[d]]] = d\n",
    "                buf[s[d]] += 1\n",
    "            buf = sum_l.copy()\n",
    "            sa[buf[s[n - 1]]] = n - 1\n",
    "            buf[s[n - 1]] += 1\n",
    "            for i in range(n):\n",
    "                v = sa[i]\n",
    "                if v >= 1 and not ls[v - 1]:\n",
    "                    sa[buf[s[v - 1]]] = v - 1\n",
    "                    buf[s[v - 1]] += 1\n",
    "            buf = sum_l.copy()\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                v = sa[i]\n",
    "                if v >= 1 and ls[v - 1]:\n",
    "                    buf[s[v - 1] + 1] -= 1\n",
    "                    sa[buf[s[v - 1] + 1]] = v - 1\n",
    "        return sa\n",
    "    def suffix_array(self, s, upper=2*10**5+10):\n",
    "        if type(s) is str:\n",
    "            s = [ord(c) for c in s]\n",
    "        return self.sa_is(s, upper)\n",
    "    def _count_sort(self, ls):\n",
    "        c = defaultdict(list)\n",
    "        for i, v in enumerate(ls):\n",
    "            c[v].append(i)\n",
    "        ans = []\n",
    "        for v in sorted(list(c.keys())):\n",
    "            for k in c[v]:\n",
    "                ans.append((k, v))\n",
    "        return ans\n",
    "    def _rk(self, sa):\n",
    "        rk = [0 for _ in sa]\n",
    "        for i in range(len(sa)):\n",
    "            rk[sa[i]] = i\n",
    "        return rk\n",
    "\n",
    "    def _height(self, s):\n",
    "        sa, rk = self.sa, self.rk\n",
    "        ht = [0] * len(sa)\n",
    "        k = 0\n",
    "        for sai in range(0, len(s)):\n",
    "            if k:\n",
    "                k -= 1\n",
    "            while True:\n",
    "                ai, bi = sai + k, sa[rk[sai] - 1] + k\n",
    "                if not (0 <= ai < len(s) and 0 <= bi < len(s)):\n",
    "                    break\n",
    "                if max(ai, bi) >= len(s):\n",
    "                    break\n",
    "                elif s[ai] == s[bi]:\n",
    "                    k += 1\n",
    "                else:\n",
    "                    break\n",
    "            ht[rk[sai]] = k\n",
    "        return ht\n",
    "    def __init__(self, s):             #下方的i都从1开始，字典序\n",
    "        if type(s) is str:             #表示排名第i小的后缀在原字符串中的起始位置为sa[i]\n",
    "            self.sa = self.suffix_array(s)\n",
    "        else:\n",
    "            self.sa = self.suffix_array(s[:])\n",
    "        self.rk = self._rk(self.sa)    #字符串中的每个位置i，其对应的后缀在后缀数组中的排名为rk[i]，排名从0开始\n",
    "        self.height = self._height(s)  #第i小的后缀与它前一名的后缀的最长公共前缀，其他地方也可能交lcp\n",
    "        self.height[0]=0               #在字符串为单一字符构成时(长度为1也算),heigh[0]会出错成1，按照定义应该为0\n",
    "class SparseTable:\n",
    "    def __init__(self, data: list, func=gcd):\n",
    "        # 稀疏表，O(nlogn)预处理，O(1)查询区间最值/或和/gcd\n",
    "        # 下标从0开始\n",
    "        self.func = func\n",
    "        self.st = st = [list(data)]\n",
    "        i, N = 1, len(st[0])\n",
    "        while 2 * i <= N+1:\n",
    "            qz = st[-1]\n",
    "            st.append([func(qz[j], qz[j + i]) for j in range(N - 2 * i + 1)])\n",
    "            i <<= 1\n",
    "\n",
    "    def query(self, begin: int, end: int):  # 查询闭区间[begin, end]的最大值\n",
    "        lg = (end - begin+1).bit_length() - 1\n",
    "        return self.func(self.st[lg][begin], self.st[lg][end - (1 << lg) + 1])\n",
    "class Solution:\n",
    "    def longestCommonSubpath(self, n: int, paths: List[List[int]]) -> int:\n",
    "        p=10**5+1\n",
    "        d={}\n",
    "        s=[]\n",
    "        for i in range(len(paths)):\n",
    "            for j in paths[i]:\n",
    "                d[len(s)]=i\n",
    "                s.append(j)\n",
    "            s.append(p)\n",
    "            p+=1\n",
    "        sa=SuffixArray(s)\n",
    "        st=SparseTable(sa.height,min)\n",
    "        l=r=res=0\n",
    "        cnt=defaultdict(int)\n",
    "        while r<len(s):\n",
    "            if sa.sa[r] in d:\n",
    "                cnt[d[sa.sa[r]]]+=1\n",
    "            while len(cnt)==len(paths):\n",
    "                res=max(res,st.query(l+1,r))\n",
    "                if sa.sa[l] in d:\n",
    "                    cnt[d[sa.sa[l]]]-=1\n",
    "                    if cnt[d[sa.sa[l]]]==0:\n",
    "                        del cnt[d[sa.sa[l]]]\n",
    "                l+=1\n",
    "            r+=1\n",
    "        return res\n",
    "\n",
    "        \n",
    "        \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
